Extensions of Fractional Precolorings Show Discontinuous Behavior
Identifieur interne : 000E21 ( Main/Exploration ); précédent : 000E20; suivant : 000E22Extensions of Fractional Precolorings Show Discontinuous Behavior
Auteurs : Jan Van Den Heuvel [Royaume-Uni] ; Daniel Král' [Royaume-Uni] ; Martin Kupec [République tchèque] ; Jean-Sébastien Sereni [République tchèque, France] ; Jan Volec [République tchèque, Royaume-Uni]Source :
- Journal of Graph Theory [ 0364-9024 ] ; 2014-12.
Abstract
We study the following problem: given a real number k and an integer d, what is the smallest ε such that any fractional (k+ɛ)‐precoloring of vertices at pairwise distances at least d of a fractionally k‐colorable graph can be extended to a fractional (k+ɛ)‐coloring of the whole graph? The exact values of ε were known for k∈{2}∪[3,∞) and any d. We determine the exact values of ε for k∈(2,3) if d=4, and k∈[2.5,3) if d=6, and give upper bounds for k∈(2,3) if d=5,7, and k∈(2,2.5) if d=6. Surprisingly, ε viewed as a function of k is discontinuous for all those values of d.
Url:
DOI: 10.1002/jgt.21787
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002994
- to stream Istex, to step Curation: 002957
- to stream Istex, to step Checkpoint: 000032
- to stream Main, to step Merge: 000E13
- to stream Main, to step Curation: 000E21
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Extensions of Fractional Precolorings Show Discontinuous Behavior</title><author><name sortKey="Van Den Heuvel, Jan" sort="Van Den Heuvel, Jan" uniqKey="Van Den Heuvel J" first="Jan" last="Van Den Heuvel">Jan Van Den Heuvel</name></author><author><name sortKey="Kral, Daniel" sort="Kral, Daniel" uniqKey="Kral D" first="Daniel" last="Král'">Daniel Král'</name></author><author><name sortKey="Kupec, Martin" sort="Kupec, Martin" uniqKey="Kupec M" first="Martin" last="Kupec">Martin Kupec</name></author><author><name sortKey="Sereni, Jean Ebastien" sort="Sereni, Jean Ebastien" uniqKey="Sereni J" first="Jean-Sébastien" last="Sereni">Jean-Sébastien Sereni</name></author><author><name sortKey="Volec, Jan" sort="Volec, Jan" uniqKey="Volec J" first="Jan" last="Volec">Jan Volec</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:B0F2458D88A6BC2FF3A23E1023E674338DEF0426</idno><date when="2014" year="2014">2014</date><idno type="doi">10.1002/jgt.21787</idno><idno type="url">https://api.istex.fr/ark:/67375/WNG-G45DWC2Q-8/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002994</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002994</idno><idno type="wicri:Area/Istex/Curation">002957</idno><idno type="wicri:Area/Istex/Checkpoint">000032</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000032</idno><idno type="wicri:doubleKey">0364-9024:2014:Van Den Heuvel J:extensions:of:fractional</idno><idno type="wicri:Area/Main/Merge">000E13</idno><idno type="wicri:Area/Main/Curation">000E21</idno><idno type="wicri:Area/Main/Exploration">000E21</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main">Extensions of Fractional Precolorings Show Discontinuous Behavior</title><author><name sortKey="Van Den Heuvel, Jan" sort="Van Den Heuvel, Jan" uniqKey="Van Den Heuvel J" first="Jan" last="Van Den Heuvel">Jan Van Den Heuvel</name><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation><affiliation wicri:level="3"><country xml:lang="fr" wicri:curation="lc">Royaume-Uni</country><wicri:regionArea>DEPARTMENT OF MATHEMATICS, LONDON SCHOOL OF ECONOMICS, WC2A 2AE, LONDON</wicri:regionArea><placeName><settlement type="city">Londres</settlement><region type="country">Angleterre</region><region type="région" nuts="1">Grand Londres</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation></author><author><name sortKey="Kral, Daniel" sort="Kral, Daniel" uniqKey="Kral D" first="Daniel" last="Král'">Daniel Král'</name><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation><affiliation wicri:level="1"><country xml:lang="fr" wicri:curation="lc">Royaume-Uni</country><wicri:regionArea>MATHEMATICS INSTITUTE DIMAP AND DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF WARWICK, CV4 7AL, COVENTRY</wicri:regionArea><wicri:noRegion>COVENTRY</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation></author><author><name sortKey="Kupec, Martin" sort="Kupec, Martin" uniqKey="Kupec M" first="Martin" last="Kupec">Martin Kupec</name><affiliation wicri:level="1"><country wicri:rule="url">République tchèque</country></affiliation><affiliation wicri:level="1"><country xml:lang="fr" wicri:curation="lc">République tchèque</country><wicri:regionArea>COMPUTER SCIENCE INSTITUTE, FACULTY OF MATHEMATICS AND PHYSICS, CHARLES UNIVERSITY, PRAGUE</wicri:regionArea><wicri:noRegion>PRAGUE</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">République tchèque</country></affiliation></author><author><name sortKey="Sereni, Jean Ebastien" sort="Sereni, Jean Ebastien" uniqKey="Sereni J" first="Jean-Sébastien" last="Sereni">Jean-Sébastien Sereni</name><affiliation wicri:level="1"><country wicri:rule="url">République tchèque</country></affiliation><affiliation wicri:level="1"><country xml:lang="fr" wicri:curation="lc">France</country><wicri:regionArea>CNRS (LORIA), VANDŒUVRE‐LÈS‐NANCY</wicri:regionArea><wicri:noRegion>VANDŒUVRE‐LÈS‐NANCY</wicri:noRegion><wicri:noRegion>VANDŒUVRE‐LÈS‐NANCY</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">République tchèque</country></affiliation></author><author><name sortKey="Volec, Jan" sort="Volec, Jan" uniqKey="Volec J" first="Jan" last="Volec">Jan Volec</name><affiliation wicri:level="1"><country wicri:rule="url">République tchèque</country></affiliation><affiliation wicri:level="1"><country xml:lang="fr" wicri:curation="lc">Royaume-Uni</country><wicri:regionArea>MATHEMATICS INSTITUTE AND DIMAP, UNIVERSITY OF WARWICK, COVENTRY CV4 7AL</wicri:regionArea><wicri:noRegion>COVENTRY CV4 7AL</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">République tchèque</country></affiliation></author></analytic><monogr></monogr><series><title level="j" type="main">Journal of Graph Theory</title><title level="j" type="alt">JOURNAL OF GRAPH THEORY</title><idno type="ISSN">0364-9024</idno><idno type="eISSN">1097-0118</idno><imprint><biblScope unit="vol">77</biblScope><biblScope unit="issue">4</biblScope><biblScope unit="page" from="299">299</biblScope><biblScope unit="page" to="329">329</biblScope><biblScope unit="page-count">31</biblScope><date type="published" when="2014-12">2014-12</date></imprint><idno type="ISSN">0364-9024</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0364-9024</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract">We study the following problem: given a real number k and an integer d, what is the smallest ε such that any fractional (k+ɛ)‐precoloring of vertices at pairwise distances at least d of a fractionally k‐colorable graph can be extended to a fractional (k+ɛ)‐coloring of the whole graph? The exact values of ε were known for k∈{2}∪[3,∞) and any d. We determine the exact values of ε for k∈(2,3) if d=4, and k∈[2.5,3) if d=6, and give upper bounds for k∈(2,3) if d=5,7, and k∈(2,2.5) if d=6. Surprisingly, ε viewed as a function of k is discontinuous for all those values of d.</div></front></TEI><affiliations><list><country><li>France</li><li>Royaume-Uni</li><li>République tchèque</li></country><region><li>Angleterre</li><li>Grand Londres</li></region><settlement><li>Londres</li></settlement></list><tree><country name="Royaume-Uni"><noRegion><name sortKey="Van Den Heuvel, Jan" sort="Van Den Heuvel, Jan" uniqKey="Van Den Heuvel J" first="Jan" last="Van Den Heuvel">Jan Van Den Heuvel</name></noRegion><name sortKey="Kral, Daniel" sort="Kral, Daniel" uniqKey="Kral D" first="Daniel" last="Král'">Daniel Král'</name><name sortKey="Kral, Daniel" sort="Kral, Daniel" uniqKey="Kral D" first="Daniel" last="Král'">Daniel Král'</name><name sortKey="Kral, Daniel" sort="Kral, Daniel" uniqKey="Kral D" first="Daniel" last="Král'">Daniel Král'</name><name sortKey="Van Den Heuvel, Jan" sort="Van Den Heuvel, Jan" uniqKey="Van Den Heuvel J" first="Jan" last="Van Den Heuvel">Jan Van Den Heuvel</name><name sortKey="Van Den Heuvel, Jan" sort="Van Den Heuvel, Jan" uniqKey="Van Den Heuvel J" first="Jan" last="Van Den Heuvel">Jan Van Den Heuvel</name><name sortKey="Volec, Jan" sort="Volec, Jan" uniqKey="Volec J" first="Jan" last="Volec">Jan Volec</name></country><country name="République tchèque"><noRegion><name sortKey="Kupec, Martin" sort="Kupec, Martin" uniqKey="Kupec M" first="Martin" last="Kupec">Martin Kupec</name></noRegion><name sortKey="Kupec, Martin" sort="Kupec, Martin" uniqKey="Kupec M" first="Martin" last="Kupec">Martin Kupec</name><name sortKey="Kupec, Martin" sort="Kupec, Martin" uniqKey="Kupec M" first="Martin" last="Kupec">Martin Kupec</name><name sortKey="Sereni, Jean Ebastien" sort="Sereni, Jean Ebastien" uniqKey="Sereni J" first="Jean-Sébastien" last="Sereni">Jean-Sébastien Sereni</name><name sortKey="Sereni, Jean Ebastien" sort="Sereni, Jean Ebastien" uniqKey="Sereni J" first="Jean-Sébastien" last="Sereni">Jean-Sébastien Sereni</name><name sortKey="Volec, Jan" sort="Volec, Jan" uniqKey="Volec J" first="Jan" last="Volec">Jan Volec</name><name sortKey="Volec, Jan" sort="Volec, Jan" uniqKey="Volec J" first="Jan" last="Volec">Jan Volec</name></country><country name="France"><noRegion><name sortKey="Sereni, Jean Ebastien" sort="Sereni, Jean Ebastien" uniqKey="Sereni J" first="Jean-Sébastien" last="Sereni">Jean-Sébastien Sereni</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000E21 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000E21 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:B0F2458D88A6BC2FF3A23E1023E674338DEF0426
|texte= Extensions of Fractional Precolorings Show Discontinuous Behavior
}}
| This area was generated with Dilib version V0.6.33. |  |